package _08_DFS_BFS;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class _200_岛屿数量 {

    public static void main(String[] args) {
        _200_岛屿数量 v = new _200_岛屿数量();
        char[][] ins = new char[][]{
                {'1', '1', '1', '1', '0'},
                {'1', '1', '0', '1', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '0', '0', '0'}
        };
        System.out.println(v.numIslands(ins));
        for (char[] in : ins) {
            System.out.println(Arrays.toString(in));
        }
    }

    public int numIslands(char[][] grid) {
        int count = 0;
        for (int rows = 0; rows < grid.length; rows++) {
            for (int cols = 0; cols < grid[rows].length; cols++) {
                if (grid[rows][cols] == '0') continue;
                // 广度优先
                bfs(grid, rows, cols);
                count++;
            }
        }
        return count;
    }

    private void bfs(char[][] grid, int row, int col) {
        if (row >= 0 && row < grid.length && col >= 0 && col < grid[row].length && grid[row][col] == '1') {
            grid[row][col] = '0';
            // 进行递归搜索
            bfs(grid, row - 1, col);
            bfs(grid, row + 1, col);
            bfs(grid, row, col + 1);
            bfs(grid, row , col - 1);
        }
    }
}
